\chapter{Quantum states and measurements}
\label{ch:quantum_states_and_measurements}
In this chapter we'll explain how to set up quantum states using
linear algebra. This will allow me to talk about quantum \emph{circuits}
in the next chapter, which will set the stage for Shor's algorithm.

I won't do very much physics (read: none at all).
That is, I'll only state what the physical reality is in terms
of linear algebras, and defer the philosophy of why this is true
to your neighborhood ``Philosophy of Quantum Mechanics'' class
(which is a ``social science'' class at MIT!).

\section{Bra-ket notation}
Physicists have their own notation for vectors:
whereas I previously used something like $v$, $e_1$, and so on,
in this chapter you'll see the infamous \vocab{bra-ket} notation:
a vector will be denoted by $\ket\bullet$, where $\bullet$ is some
variable name: unlike in math or Python, this can include
numbers, symbols, Unicode characters, whatever you like.
This is called a ``ket''.
To pay a homage to physicists everywhere,
we'll use this notation for this chapter too.

\begin{abuse}
	[For this part, $\dim H < \infty$]
	In this part on quantum computation,
	we'll use the word ``Hilbert space'' as defined earlier,
	but in fact all our Hilbert spaces will be finite-dimensional.
\end{abuse}

If $\dim H = n$, then its orthonormal basis elements are often denoted
\[ \ket0, \ket1, \dots, \ket{n-1} \]
(instead of $e_i$)
and a generic element of $H$ denoted by
\[ \ket\psi, \ket\phi, \dots \]
and various other Greek letters.

Now for any $\ket\psi \in H$,
we can consider the canonical dual element in $H^\vee$
(since $H$ has an inner form), which we denote by $\bra\psi$ (a ``bra'').
For example, if $\dim H = 2$ then we can write
\[ \ket\psi = \begin{bmatrix} \alpha \\ \beta \end{bmatrix} \]
in an orthonormal basis, in which case
\[ \bra\psi = \begin{bmatrix} \ol\alpha & \ol\beta \end{bmatrix}. \]
We even can write dot products succinctly in this notation:
if $\ket\phi = \begin{bmatrix} \gamma \\ \delta \end{bmatrix}$,
then the dot product of $\bra\psi$ and $\ket\phi$ is given by
\[
	\braket{\psi|\phi}
	= \cvec{\ol\alpha & \ol\beta} \cvec{\gamma \\ \delta}
	= \ol\alpha\gamma + \ol\beta \delta.
\]
So we will use the notation $\braket{\psi|\phi}$
instead of the more mathematical $\left< \ket\psi, \ket\phi \right>$.
In particular, the squared norm of $\ket\psi$ is just $\braket{\psi|\psi}$.
Concretely, for $\dim H = 2$ we have
$\braket{\psi|\psi} = |\alpha|^2 + |\beta|^2$.

\section{The state space}
If you think that's weird, well, it gets worse.

In classical computation, a bit is either $0$ or $1$.
More generally, we can think of a classical space of $n$
possible states $0$, \dots, $n-1$.
Thus in the classical situation, the space of possible states
is just a discrete set with $n$ elements.

In quantum computation, a \vocab{qubit} is instead
any \emph{complex linear combination} of $0$ and $1$.
To be precise, consider the normed complex vector space
\[ H = \CC^{\oplus 2} \]
and denote the orthonormal basis elements by $\ket0$ and $\ket1$.
Then a \emph{qubit} is a nonzero element $\ket\psi \in H$,
so that it can be written in the form
\[ \ket\psi = \alpha \ket 0 + \beta \ket 1 \]
where $\alpha$ and $\beta$ are not both zero.
Typically, we normalize so that $\ket\psi$ has norm $1$:
\[ \braket{\psi|\psi} = 1 \iff |\alpha|^2 + |\beta|^2 = 1. \]
In particular, we can recover the ``classical'' situation
with $\ket 0 \in H$ and $\ket 1 \in H$,
but now we have some ``intermediate'' states,
such as \[ \frac{1}{\sqrt2} \left(\ket 0 + \ket 1 \right). \]
Philosophically, what has happened is that:
\begin{moral}
	Instead of allowing just the states $\ket 0$ and $\ket 1$,
	we allow any complex linear combination of them.
\end{moral}
More generally, if $\dim H = n$,
then the possible states are nonzero elements
\[ c_0\ket0 + c_1\ket1 + \dots + c_{n-1}\ket{n-1} \]
which we usually normalize so that
$|c_0|^2 + |c_1|^2 + \dots + |c_{n-1}|^2 = 1$.

\section{Observations}
\prototype{$\id$ corresponds to not making a measurement
	since all its eigenvalues are equal,
	but any operator with distinct eigenvalues will cause collapse.}
If you think that's weird, well, it gets worse.
First, some linear algebra review (\Cref{def:hermitian}):
\begin{definition}
	Let $V$ be a finite-dimensional inner product space.
	For a map $T \colon V \to V$, the following conditions are equivalent:
	\begin{itemize}
		\ii $\left< Tx, y\right> = \left< x, Ty \right>$
		for any $x,y \in V$.
		\ii $T = T^\dagger$.
	\end{itemize}
	A map $T$ satisfying these conditions is called \vocab{Hermitian}.
\end{definition}
\begin{ques}
	Show that $T$ is normal.
\end{ques}
Thus, we know that $T$ is diagonalizable
with respect to the inner form, so for a suitable basis we
can write it in an orthonormal basis as
\[
	T = \begin{bmatrix}
		\lambda_0 & 0 & \dots & 0 \\
		0 & \lambda_1 & \dots & 0 \\
		\vdots & \vdots & \ddots & \vdots \\
		0 & 0 & \dots & \lambda_{n-1}
	\end{bmatrix}.
\]
As we've said, this is fantastic:
not only do we have a basis of eigenvectors,
but the eigenvectors are pairwise orthogonal,
and so they form an orthonormal basis of $V$.
\begin{ques}
	Show that all eigenvalues of $T$ are real.
	($T = T^\dagger$.)
\end{ques}

Back to quantum computation.
Suppose we have a state $\ket\psi \in H$, where $\dim H = 2$;
we haven't distinguished a particular basis yet,
so we just have a nonzero vector.
Then the way observations work (and this is physics, so you'll have to
take my word for it) is as follows:
\begin{moral}
	Pick a Hermitian operator $T \colon H \to H$;
	then observations of $T$ return eigenvalues of $T$.
\end{moral}
To be precise:
\begin{itemize}
	\ii Pick a Hermitian operator $T \colon H \to H$,
	which is called the \vocab{observable}.
	\ii Consider its eigenvalues $\lambda_0$, \dots, $\lambda_{n-1}$
	and corresponding eigenvectors $\ket{0}_T$, \dots, $\ket{n-1}_T$.
	Tacitly we may assume that $\ket{0}_T$, \dots, $\ket{n-1}_T$ form
	an orthonormal basis of $H$.
	(The subscript $T$ is here to distinguish the eigenvectors of $T$
	from the basis elements of $H$.)
	\ii Write $\ket\psi$ in the orthonormal basis as
	\[ c_0\ket0_T + c_1\ket1_T + \dots + c_{n-1}\ket{n-1}_T. \]
	\ii Then the probability of observing $\lambda_i$ is
	\[ \frac{|c_i|^2}{|c_0|^2 + \dots + |c_{n-1}|^2}. \]
	This is called making an \vocab{observation along $T$}.
\end{itemize}
Note that in particular, for any nonzero constant $c$,
$\ket\psi$ and $c\ket\psi$ are indistinguishable,
which is why we like to normalize $\ket\psi$.
But the queerest thing of all is what happens to $\ket\psi$:
by measuring it, we actually destroy information.
This behavior is called \vocab{quantum collapse}.
\begin{itemize}
	\ii Suppose for simplicity that we observe $\ket\psi$
	with $T$ and obtain an eigenvalue $\lambda$,
	and that $\ket{i}_T$ is the only eigenvector with this eigenvalue.
	Then, the state $\ket\psi$ \emph{collapses} to just the state
	$c_i \ket{i}_T$: all the other information is destroyed.
	(In fact, we may as well say it collapses to $\ket{i}_T$,
	since again constant factors are not relevant.)

	\ii	More generally, if we observe $\lambda$,
	consider the generalized eigenspace $H_\lambda$
	(i.e.\ the span of eigenvectors with the same eigenvalue).
	Then the physical state $\ket\psi$ has been changed as well:
	it has now been projected onto the eigenspace $H_\lambda$.
	In still other words, after observation, the state collapses to
	\[
		\sum_{\substack{0 \le i \le n \\ \substack{\lambda_i = \lambda}}}
		c_i \ket{i}_T.
	\]
\end{itemize}
In other words,
\begin{moral}
	When we make a measurement,
	the coefficients from different eigenspaces are destroyed.
\end{moral}
Why does this happen? Beats me\dots\ physics (and hence real life) is weird.
But anyways, an example.
\begin{example}
	[Quantum measurement of a state $\ket\psi$]
	Let $H = \CC^{\oplus 2}$ with orthonormal basis $\ket0$ and $\ket1$
	and consider the state
	\[
		\ket\psi
		= \frac{i}{\sqrt5} \ket 0
		+ \frac{2}{\sqrt5} \ket 1
		= \pair{i/\sqrt5}{2/\sqrt5} \in H.
	\]
	\begin{enumerate}[(a)]
		\ii Let \[ T = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}. \]
		This has eigenvectors $\ket0 = \ket0_T$ and $\ket1 = \ket1_T$,
		with eigenvalues $+1$ and $-1$.  So if we measure $\ket\psi$ to $T$,
		we get $+1$ with probability $1/5$ and $-1$ with probability $4/5$.
		After this measurement, the original state collapses to
		$\ket0$ if we measured $+1$, and $\ket1$ if we measured $-1$.
		So we never learn the original probabilities.

		\ii Now consider $T = \id$, and arbitrarily
		pick two orthonormal eigenvectors $\ket0_T$, $\ket1_T$;
		thus $\psi = c_0\ket0_T + c_1\ket1_T$.
		Since all eigenvalues of $T$ are $+1$,
		our measurement will always be $+1$ no matter what we do.
		But there is also no collapsing,
		because none of the coefficients get destroyed.

		\ii Now consider
		\[ T = \begin{bmatrix} 0 & 7 \\ 7 & 0 \end{bmatrix}. \]
		The two normalized eigenvectors are
		\[ \ket0_T = \frac{1}{\sqrt2}\pair11
		\qquad \ket1_T = \frac{1}{\sqrt2}\pair1{-1} \]
		with eigenvalues $+7$ and $-7$ respectively. In this basis, we have
		\[
			\ket\psi = \frac{2+i}{\sqrt{10}}\ket0_T
			+ \frac{-2+i}{\sqrt{10}}\ket1_T. \]
		So we get $+7$ with probability $\half$ and $-7$
		with probability $\half$, and after the measurement,
		$\ket\psi$ collapses to one of $\ket0_T$ and $\ket1_T$.
	\end{enumerate}
\end{example}
\begin{ques}
	Suppose we measure $\ket\psi$ with $T$ and get $\lambda$.
	What happens if we measure with $T$ again?
\end{ques}

For $H = \CC^{\oplus 2}$ we can come up with more classes of examples using
the so-called \vocab{Pauli matrices}.
These are the three Hermitian matrices
\[
	\sigma_z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}
	\qquad
	\sigma_x = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}
	\qquad
	\sigma_y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}.
\]

These matrices are important because:
\begin{ques}
	Show that these three matrices, plus the identity matrix,
	form a basis for the set of Hermitian $2 \times 2$ matrices.
\end{ques}
So the Pauli matrices are a natural choice of basis.\footnote{Well,
	natural due to physics reasons.
}

Their normalized eigenvectors are
\[ \zup = \ket0 = \pair10 \qquad \zdown = \ket1 = \pair01 \]
\[ \xup = \frac{1}{\sqrt2}\pair11
	\qquad \xdown = \frac{1}{\sqrt2}\pair1{-1} \]
\[ \yup = \frac{1}{\sqrt2}\pair1i
	\qquad \ydown = \frac{1}{\sqrt2}\pair1{-i} \]
which we call ``$z$-up'', ``$z$-down'',
``$x$-up'', ``$x$-down'', ``$y$-up'', ``$y$-down'' respectively.
(The eigenvalues are $+1$ for ``up'' and $-1$ for ``down''.)
So, given a state $\ket\psi \in \CC^{\oplus 2}$
we can make a measurement with respect to any of these three bases
by using the corresponding Pauli matrix.

In light of this, the previous examples were
(a) measuring along $\sigma_z$,
(b) measuring along $\id$,
and (c) measuring along $7\sigma_x$.

Notice that if we are given a state $\ket\psi$,
and are told in advance that it is either $\xup$ or $\xdown$
(or any other orthogonal states)
then we are in what is more or less a classical situation.
Specifically, if we make a measurement along $\sigma_x$,
then we find out which state that $\ket\psi$ was in (with 100\% certainty),
and the state does not undergo any collapse.
Thus, orthogonal states are reliably distinguishable.

\section{Entanglement}
\prototype{Singlet state: spooky action at a distance.}
If you think that's weird, well, it gets worse.

Qubits don't just act independently:
they can talk to each other by means of a \emph{tensor product}.
Explicitly, consider \[ H = \CC^{\oplus 2} \otimes \CC^{\oplus 2} \]
endowed with the norm described in \Cref{prob:inner_prod_tensor}.
One should think of this as a qubit $A$ in a space $H_A$
along with a second qubit $B$ in a different space $H_B$,
which have been allowed to interact in some way,
and $H = H_A \otimes H_B$ is the set of possible states of \emph{both} qubits.
Thus
\[
	\ket{0}_A \otimes \ket{0}_B, \quad
	\ket{0}_A \otimes \ket{1}_B, \quad
	\ket{1}_A \otimes \ket{0}_B, \quad
	\ket{1}_A \otimes \ket{1}_B
\]
is an orthonormal basis of $H$;
here $\ket{i}_A$ is the basis of the first $\CC^{\oplus 2}$
while $\ket{i}_B$ is the basis of the second $\CC^{\oplus 2}$,
so these vectors should be thought of as ``unrelated''
just as with any tensor product.
The pure tensors mean exactly what you want:
for example $\ket0_A \otimes \ket1_B$ means
``$0$ for qubit $A$ and $1$ for qubit $B$''.

As before, a measurement of a state in $H$ requires
a Hermitian map $H \to H$.
In particular, if we only want to measure the qubit $B$ along $M_B$,
we can use the operator \[ \id_A \otimes M_B. \]
The eigenvalues of this operator coincide with the ones for $M_B$,
and the eigenspace for $\lambda$ will be the $H_A \otimes (H_B)_\lambda$,
so when we take the projection the $A$ qubit will be unaffected.

This does what you would hope for pure tensors in $H$:
\begin{example}[Two non-entangled qubits]
	Suppose we have qubit $A$ in the state
	$\frac{i}{\sqrt5}\ket0_A + \frac{2}{\sqrt5}\ket1_A$
	and qubit $B$ in the state
	$\frac{1}{\sqrt2} \ket0_B + \frac{1}{\sqrt2}\ket1_B$.
	So, the two qubits in tandem are represented by the pure tensor
	\[
		\ket\psi
		=
		\left( \frac{i}{\sqrt5}\ket0_A + \frac{2}{\sqrt5}\ket1_A \right)
		\otimes
		\left( \frac{1}{\sqrt2} \ket0_B + \frac{1}{\sqrt2}\ket1_B \right).
	\]
	Suppose we measure $\ket\psi$ along
	\[ M = \id_A \otimes \sigma_z^B. \]
	The eigenspace decomposition is
	\begin{itemize}
		\ii $+1$ for the span of $\ket0_A \otimes \ket0_B$ and
		$\ket1_A \otimes \ket0_B$, and
		\ii $-1$ for the span of $\ket0_A \otimes \ket1_B$ and
		$\ket1_A \otimes \ket1_B$.
	\end{itemize}
	(We could have used other bases, like $\xup_A \otimes \ket0_B$ and
	$\xdown_A \otimes \ket0_B$ for the first eigenspace, but it doesn't matter.)
	Expanding $\ket\psi$ in the four-element basis, we find that
	we'll get the first eigenspace with probability
	\[ \left|\frac{i}{\sqrt{10}}\right|^2
	+ \left|\frac{2}{\sqrt{10}}\right|^2 = \half. \]
	and the second eigenspace with probability $\half$ as well.
	(Note how the coefficients for $A$ don't do anything!)
	After the measurement, we destroy the coefficients of the other eigenspace;
	thus (after re-normalization) we obtain the collapsed state
	\[ \left( \frac{i}{\sqrt5}\ket0_A + \frac{2}{\sqrt5}\ket1_A \right)
		\otimes \ket0_B
		\qquad\text{or}\qquad
		\left( \frac{i}{\sqrt5}\ket0_A + \frac{2}{\sqrt5}\ket1_A \right)
		\otimes \ket1_B
	\]
	again with 50\% probability each.
\end{example}
So this model lets us more or less work with the two qubits independently:
when we make the measurement, we just make sure to not touch the other qubit
(which corresponds to the identity operator).

\begin{exercise}
	Show that if $\id_A \otimes \sigma_x^B$ is applied to the $\ket\psi$
	in this example, there is no collapse at all.
	What's the result of this measurement?
\end{exercise}

Since the $\otimes$ is getting cumbersome to write, we say:
\begin{abuse}
	From now on $\ket 0_A \otimes \ket 0_B$ will be abbreviated
	to just $\ket{00}$, and similarly for $\ket{01}$, $\ket{10}$, $\ket{11}$.
\end{abuse}

\begin{example}
	[Simultaneously measuring a general $2$-Qubit state]
	\label{ex:simult_measurement}
	Consider a normalized state $\ket\psi$ in
	$H = \CC^{\oplus 2} \otimes \CC^{\oplus 2}$, say
	\[ \ket\psi = \alpha\ket{00} + \beta\ket{01}
		+ \gamma\ket{10} + \delta\ket{11}. \]
	We can make a measurement along the diagonal matrix
	$T \colon H \to H$ with
	\[ T(\ket{00}) = 0\ket{00}, \quad
	T(\ket{01}) = 1\ket{01}, \quad
	T(\ket{10}) = 2\ket{10}, \quad
	T(\ket{11}) = 3\ket{11}. \]
	Thus we get each of the eigenvalues $0$, $1$, $2$, $3$
	with probability $|\alpha|^2$, $|\beta|^2$, $|\gamma|^2$, $|\delta|^2$.
	So if we like we can make ``simultaneous'' measurements on two qubits
	in the same way that we make measurements on one qubit.
\end{example}

However, some states behave very weirdly.
\begin{example}[The singlet state]
	Consider the state
	\[
		\ket{\Psi_-}
		=
		\frac{1}{\sqrt2} \ket{01}
		- \frac{1}{\sqrt2} \ket{10}
	\]
	which is called the \vocab{singlet state}.
	One can see that $\ket{\Psi_-}$ is not a simple tensor,
	which means that it doesn't just consist of two qubits side by side:
	the qubits in $H_A$ and $H_B$ have become \emph{entangled}.

	Now, what happens if we measure just the qubit $A$?
	This corresponds to making the measurement
	\[ T = \sigma_z^A \otimes \id_B. \]
	The eigenspace decomposition of $T$ can be described as:
	\begin{itemize}
		\ii The span of $\ket{00}$ and $\ket{01}$, with eigenvalue $+1$.
		\ii The span of $\ket{10}$ and $\ket{11}$, with eigenvalue $-1$.
	\end{itemize}
	So one of two things will happen:
	\begin{itemize}
		\ii With probability $\half$, we measure $+1$
		and the collapsed state is $\ket{01}$.
		\ii With probability $\half$, we measure $-1$
		and the collapsed state is $\ket{10}$.
	\end{itemize}
	But now we see that measurement along $A$ has told us what the
	state of the bit $B$ is completely!
\end{example}
By solely looking at measurements on $A$, we learn $B$;
this paradox is called \emph{spooky action at a distance},
or in Einstein's tongue, \vocab{spukhafte Fernwirkung}.
Thus,
\begin{moral}
	In tensor products of Hilbert spaces,
	states which are not pure tensors
	correspond to ``entangled'' states.
\end{moral}

What this really means is that the qubits cannot be described independently;
the state of the system must be given as a whole.
That's what entangled states mean: the qubits somehow depend on each other.

\section\problemhead

\begin{problem}
	We measure $\ket{\Psi_-}$ by $\sigma_x^A \otimes \id_B$,
	and hence obtain either $+1$ or $-1$.
	Determine the state of qubit $B$ from this measurement.
	\begin{hint}
		Rewrite $\ket{\Psi_-} = -\frac{1}{\sqrt2}
		\left( \xup_A\otimes\xdown_B - \xdown_A\xup_B \right)$.
	\end{hint}
	\begin{sol}
		By a straightforward computation,
		we have $\ket{\Psi_-} = -\frac{1}{\sqrt2}
		\left( \xup_A\otimes\xdown_B - \xdown_A\xup_B \right)$.
		Now, $\xup_A \otimes \xup_B$, $\xup_A \otimes \xdown_B$
		span one eigenspace of $\sigma_x^A \otimes \id_B$,
		and $\xdown_A \otimes \xup_B$, $\xdown_A \otimes \xdown_B$
		span the other. So this is the same as before:
		$+1$ gives $\xdown_B$ and $-1$ gives $\xdown_A$.
	\end{sol}
\end{problem}

\begin{problem}
	[Greenberger-Horne-Zeilinger paradox]
	Consider the state in $(\CC^{\oplus2})^{\otimes 3}$
	\[
		\ket{\Psi}_{\text{GHZ}}
		=
		\frac{1}{\sqrt2}
		\left( \ket0_A \ket0_B \ket0_C
		- \ket1_A \ket1_B \ket1_C \right).
	\]
	Find the value of the measurements along each of
	\[ \sigma_y^A \otimes \sigma_y^B \otimes \sigma_x^C , \quad
		\sigma_y^A \otimes \sigma_x^B \otimes \sigma_y^C, \quad
		\sigma_x^A \otimes \sigma_y^B \otimes \sigma_y^C, \quad
		\sigma_x^A \otimes \sigma_x^B \otimes \sigma_x^C.
	\]
	As for the paradox: what happens if you multiply all these measurements together?
	\begin{hint}
		$1$, $1$, $1$, $-1$ respectively.
		When we multiply them all together,
		we get that $\id^A \otimes \id^B \otimes \id^C$
		has measurement $-1$, which is the paradox.
		What this means is that the values of the measurements
		can't be prepared in advance independently.
		In other words, this contradicts certain local hidden-variable theories.

		This was one of several results for which Zeilinger won a (shared)
		Nobel Prize in 2022.
	\end{hint}
\end{problem}
